package cxydmmszl.chapter04.t068;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 最小编辑代价
 * <li style="color: green;">Desc</li>
 * 给定两个字符串str1和str2，再给定三个整数 ic，dc 和 rc，分别代表插入、删除和替换一个字符的代价，
 * 请输出将 str1 编辑成 str2 的最小代价。
 * <li style="color: green;">Input</li>
 * 输出三行，第一行和第二行均为一行字符串，分别表示两个字符串
 * str1，str2。(1<=length(str1), length(str2)<=5000)。
 * 第三行为三个正整数，代表ic，dc和rc。（1<=ic<=10000、1<=dc<=10000、1<=rc<=10000）
 * <li style="color: green;">Output</li>
 * 输出一个整数，表示编辑的最小代价。
 * <li style="color: blue;">Link</li> CD43
 *
 * @author habitplus
 * @since 2021-09-13 21:14
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine().trim();
        String str2 = br.readLine().trim();
        String[] ss = br.readLine().split(" ");
        br.close();
        int ic = Integer.parseInt(ss[0]);
        int dc = Integer.parseInt(ss[1]);
        int rc = Integer.parseInt(ss[2]);

        int ans = minEditCost(str1, str2, ic, dc, rc);
        System.out.println(ans);
    }

    private static int minEditCost(String str1, String str2, int ic, int dc, int rc) {
        if (str1 == null || str2 == null) {
            return 0;
        }

        char[] chs1 = str1.toCharArray();
        char[] chs2 = str2.toCharArray();
        int n = chs1.length;
        int m = chs2.length;
        // dp[i][j] 表示将 str1[0,i-1] 编辑成 str2[0,j-1] 的最小代价
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= m; i++) {
            // 只能添加
            dp[0][i] = ic * i;
        }

        for (int i = 1; i <= n; i++) {
            // 只能删除
            dp[i][0] = dc * i;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 四种情况取最小值
                if (chs1[i - 1] == chs2[j - 1]) {
                    // 只需将 str1[0,i-2] 编辑成 str2[0, j-2] 即可
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 将 str1[0,i-2] 编辑成 str2[0, j-2]，再将 str1[i-1] 替换为 str2[j-2]
                    dp[i][j] = dp[i - 1][j - 1] + rc;
                }
                // 将str1[0,i-1] 编辑成 str2[0,j-2]，并增加 str2[j-1]
                dp[i][j] = Math.min(dp[i][j - 1] + ic, dp[i][j]);
                // 将str1[0,i-2] 编辑成 str2[0,j-1]，并删除 str1[i-1]
                dp[i][j] = Math.min(dp[i - 1][j] + dc, dp[i][j]);
            }
        }
        return dp[n][m];
    }
}
